#include "FifteenPuzzle.h"
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <random>       
#include <chrono>
#include <conio.h>
#include <string>
using namespace std;
HighScore FifteenPuzzle::scores;

static const string savefile = "highscores.txt";

bool checkIfSolveable(vector<int> &);

FifteenPuzzle::FifteenPuzzle()
{
}

FifteenPuzzle::~FifteenPuzzle()
{
}
void FifteenPuzzle::runGame()
{
	scores.loadScores(savefile);
	bool gameFinished = true;
	randomizeBoard();
	moves = 0;
	drawBoard();
	while (!gameDone())
	{
		findFree();
		char input = _getch();
		//LeftArrow
		if (input == 75 && freeY < 3)
		{
			moveTiles(board[freeX][freeY], board[freeX][freeY + 1]);
		}
		//UpArrow
		else if (input == 72 && freeX < 3)
		{
			moveTiles(board[freeX][freeY], board[freeX + 1][freeY]);
		}
		//RightArrow
		else if (input == 77 && freeY > 0)
		{
			moveTiles(board[freeX][freeY], board[freeX][freeY - 1]);
		}
		//DownArrow
		else if (input == 80 && freeX > 0)
		{
			moveTiles(board[freeX][freeY], board[freeX - 1][freeY]);
		}
		else if (input == 27)
		{
			gameFinished = false;
			break;
		}
	}
	drawBoard();
	if (gameFinished){
		cout << "Puzzle solved!" << endl << "It took you " << moves << " moves." << endl;
		system("pause");
		if (moves < scores.getWorstScore())
		{
			scores.addScore(HighScore::getArcadeName(), moves);
			scores.saveScores(savefile);
		}
	}
	else
	{
		cout << "Puzzle exited after " << moves << " moves.." << endl;
	}
	scores.print();
}

void FifteenPuzzle::drawBoard()
{
	system("cls");
	for (int i = 0; i < 4; i++)
	{
		cout << "---------------------" << endl << "|";
		for (int j = 0; j < 4; j++)
		{
			cout << " ";
			if (board[i][j] == 0){
				cout << "   |";
			}
			else{
				cout << setw(2) << board[i][j] << " |";
			}
		}
		cout << endl;
	}
	cout << "---------------------" << endl;
}

void FifteenPuzzle::findFree()
{
	for (int i = 0; i < 4; i++)
	{
		for (int j = 0; j < 4; j++)
		{
			if (board[i][j] == 0)
			{
				freeX = i;
				freeY = j;
			}
		}
	}
}

bool FifteenPuzzle::gameDone()
{
	int k = 1;
	for (int i = 0; i < 4; i++)
	{
		for (int j = 0; j < 4; j++)
		{
			if (board[i][j] != k)
			{
				return false;
			}
			k = ++k % 16;
		}
	}
	return true;
}


void FifteenPuzzle::randomizeBoard()
{
	vector<int> iv = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0 };

	unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
	shuffle(iv.begin(), iv.end(), std::default_random_engine(seed));
	while (checkIfSolveable(iv) == false)
	{
		random_shuffle(iv.begin(), iv.end());
	} 

	int k = 0;
	for (int i = 0; i < 4; i++)
	{
		for (int j = 0; j < 4; j++)
		{
			board[i][j] = iv[k++];
		}
	}
}

void FifteenPuzzle::moveTiles(int &a, int &b)
{
	int tmp = a;
	a = b;
	b = tmp;
	moves++;
	drawBoard();
}

//Returns true if the current vector permutation will generate a solveable 4x4 puzzle board
bool checkIfSolveable(vector<int> &iv)
{
	int inversions = 0, emptyRow = 0;
	for (int i = 0; i < static_cast<signed int>(iv.size()); i++)
	{
		if (iv[i] == 0)
		{
			if ((i > 3 && i < 8) || i > 11)
			{
				emptyRow = 1;
			}
		}
		else
		{
			for (int j = i + 1; j < static_cast<signed int>(iv.size()); j++)
			{
				if (iv[i] > iv[j] && iv[j] != 0){
					inversions++;
				}
			}
		}
	}
	if (((inversions + emptyRow) % 2) == 1)
	{
		return true;
	}
	return false;

	/*If the grid width is odd, then the number of inversions in a solvable situation is even.
	If the grid width is even, and the blank is on an even row counting from the bottom(second - last, fourth - last etc), then the number of inversions in a solvable situation is odd.
	If the grid width is even, and the blank is on an odd row counting from the bottom(last, third - last, fifth - last etc) then the number of inversions in a solvable situation is even.*/
}